|
Safe semantics is a consistency model that describes one type of guarantee a data register provides when it is shared by several processors in a parallel machine or in a network of computers working together. This notion was first defined by Lamport in 1985.〔Lamport, Leslie. On Interprocess Communication. Palo Alto, CA: DEC Systems Research Center, 1985. Web. 21 Oct. 2013. SRC Research Report.〕 Later on, it was formally defined in Leslie Lamport's "On Interprocess Communication", which was published in ''Distributed Computing'' in 1986.〔Lamport, Leslie. “On Interprocess Communication.” Distributed Computing 1.2 (1986): 77–85. link.springer.com. Web. 21 Oct. 2013.〕 Safe semantics are defined for a variable with a single writer but multiple readers (SWMR). A SWMR register is safe if each read operation satisfies the two following properties: # A read operation not concurrent with any write operation returns the value written by the latest write operation. # A read operation that is concurrent with a write operation may return any value within the register's allowed range of values (for example, 0,1,2,...). In particular, if there is concurrency between a read and a write operation, the read operation can return a value which has never been written by any write operation. The return value only belongs to the register domain. We can see a binary safe register as modeling a bit flickering. Whatever the previous value of the register is, the register's value could flicker until the write operation finishes. Therefore, the read operation which overlaps with a write operation could return 0 r 1. There have been many implementations of safe register in distributed systems. Baldoni et al. show that there is no way to implement a register having the stronger property of regular semantics in a synchronous system under continuous churn. On the other hand, it has been demonstrated in that a safe register can be implemented under continuous churn in a non-synchronous system. Here, churn refers to the leaving and joining of servers from/into a distributed system. Modeling and Implementing a type of storage memory (Safe Register) under non-quiescent churn in required some system models such as client and server systems.Client systems contains finite arbitrary number of processes and they are responsible for reading and writing into the server system.On the other hand,the server system just make sure that read and write operations happen properly.Safe register implementation was as follow: -Safe register was maintained by the set of active servers. -Clients do not maintain any register information (trigger operation, and interact with servers) -Eventually synchronous system -Quorums(set of server or client systems) -Size of the Read() and Write() operation executed on quorums = n – f – J (n is the number of servers, J is the number of servers that leave and join,and f is the number of Byzantine failures. Before implementing the safe register,in some algorithms were introduced such as join,read, and write operation. Join Operation():A server(si) which wants to get entered into a server system will broadcast an inquiry message to other servers to inform other servers of its arrival into the distributed system,si also wants to find a current value of the register.Once other server received this inquiry they will send a reply message to si.After si receives enough reply from other servers,it will collect all the replies and saves them into a reply set.Si waits until it gets enough reply(n-f-j) from other servers then it will pick up the most frequent value among other values.Si will also do the following : -Updates its local copy of the register -It becomes active -Sends reply to the processes in the set reply -If si its active it will sends reply message to the other servers immediately. -Otherwise,if Si is not active, it will store the inquiries somewhere to reply them by the time it become active. -When si gets reply from other servers it will eventually add the new reply to the reply set and throw the old value from the reply set. -If the value of the respond server is bigger that si value, then si will update its information with the new value. Read operation(): the read operation algorithm is a basic version of the join operation.The only difference between these two algorithms is the broadcast mechanism used by the read operation.A client (cw)will broadcast a message to the system and once a server receives the inquiry,it will send a reply message to the client.Once the client receives enough replies (n-f-j) it will stop sending an inquiry. Write operation:Client(cw) sends an inquiry into the system in different rounds and it will wait until it receives two acknowledgment.(sn =sequence number) The reason for receiving two acknowledgment is because there could be a danger in a system. When a process Sends an acks, it may die after one millisecond.Therefore,there will be no confirmation received by the client. In the validity of the safe register(If a read() not concurrent with any write(), returns the last value written before its invocation) was proved based on the quorum system.Assume that there are two quorum system(Qw,Qr).Qw indicates the Servers that know about the latest value,and Qr indicates Values of Read’s responses.Based on the assumption in the size of each quorum is equal to n-f-j.To prove the safe register's validity we need to prove the following equation: (Qw∩Qr)\B >(Qr∩B) :Note that B is the number of Byzantine failures. Proof : Red region indicates (Qw∩Qr)\B and the blue region indicates Qr∩B.Based on the assumption,we know that the size of each quorum is n-f-j,so the red region will have n-3f-2j active servers.Therefore,n-3f-2J > f --> n > 4f+2J --> n is strictly greater than f. ==Notes== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「safe semantics」の詳細全文を読む スポンサード リンク
|